1. Field of the Invention
The invention relates generally to techniques of allowing real-time detection of failed inter-node links in a communication network running a specific routing protocol.
2. Description of the Related Art
Over the Internet, nodes (e.g., routers) relay packets to other nodes, according to a pre-defined routing protocol. A representative routing protocols for exchanging routing information (network reachability) among different network domains within the Internet is called BGP (Border Gateway Protocol). A domain in BGP is called AS (Autonomous System). Each domain is assigned an AS (Autonomous System) number which is unique within the Internet. Nodes within each domain are allocated the same AS number, often sharing the same routing policy under the control of the same network operator(s). Each AS number, traditionally in two bytes (but currently, shifting to four bytes), is assigned by IANA (Internet Assigned Numbers Authority).
FIG. 1A illustrates the configuration of an exemplary network using BGP, and FIG. 1B illustrates the routing table created in such network.
As illustrated in FIG. 1A, each node is allocated a unique AS number are connected using BGP. Each node creates and sends to neighboring nodes in a broadcast manner, one or more UPDATE messages containing to advertise the reachability of one or more destination prefixes (i.e., the destination network-address). Each UPDATE message includes the following parameters:
(1) Type of Message,
(2) List of Prefix(es)
(3) AS_PATH Attribute (Only for Announce messages).
The “Type of Message” refers to the type of the UPDATE message (i.e., A: announce message for advertising feasible prefixes, or W: withdraw message for withdrawing unfeasible prefixes).
The “List of Prefix(es)” implies the list of prefixes that are either announced or withdrawn, where a “prefix” refers to a combination of a network address and a subnet mask (xxx.xxx.xxx.xxx/xx).
The “AS_PATH Attribute” refers to the AS path used to reach the prefix, denoted by a sequence of AS numbers.
On receiving an UPDATE (Announce) message, each node adds its own AS number to the AS_PATH Attribute of the received UPDATE (Announce) message, and relays the modified UPDATE (Announce) message to its neighbors.
Each node maintains the list of prefixes and its AS paths in a routing table, called “RIB (Routing Information Base).” FIG. 1B illustrates an example routing table created at AS10 of FIG. 1A. The sequence of AS numbers for each prefix indicate the ASes to traverse before reaching that prefix. The routing table is updated each time a new UPDATE message is received for each prefix.
A known technique for detecting a failed link within such network analyzes the correlation of the AS paths of prefixes observed very close in time. This technique is disclosed in, for example, “A. Feldmann, O. Maennel, Z. Mao, A. Berger, and B. Maggs, “Locating Internet Routing Instabilities,” SIGCOMM 2004.”
This technique would allow network operators to estimate one or more links as the location of the failure using the prefixes that were observed during the evaluation period.
Another known technique extracts inter AS links from the AS paths attribute of each prefix, and, as illustrated in FIG. 1C, calculate the number prefixes that are used by each link. This technique is disclosed in, for example, “M. Lad, R. Oliveira, D. Massey, and L. Zhang, “Inferring the Origin of Routing Changes using Link Weights,” IEEE ICNP 2007,” and “A. Campisano, L. Cittadini, G. Di Battista, T. Refice, and C. Sasso, “Tracking Back the Root Cause of a Path Change in Interdomain Routing,” IEEE Network Operations and Management Symposium, 2008.”
This technique would allow network operators to measure the number prefixes gained or lost at each link, and estimate the link that loses all prefixes (or the number of lost prefixes is more than the predefined threshold) as the location of failure.